import typing

# 题目：实现一个函数来匹配包含'.' 和'*'， 的正则表达式，'.' 表示匹配任意一个字符， '*'表示前面的一个字符重复任意次

# 当模式中第二个字符不是’*‘时，直接匹配字符串和模式中的第一个字符，如果匹配，那么都往后移动一个字符，去匹配后面的字符串；如果不匹配那直接返回False
# 当模式中第二个字符串是’*‘时，会有多种选择：一种选择是在模式中往后移动两个字符：’*‘和前面一个字符被忽略
#                                     如果模式中第一个字符和字符串中第一个字符匹配，则在字符串上向后移动一个字符，而在模式上则可以向后移动两个字符，也可以保持不变

def match(s:str, pattern:str):
    if s == pattern:
        return True
    if not pattern:
        return False

    # 如果第二个字符是为’*‘
    if len(pattern)>1 and pattern[1]=='*':
        # 判断首字符是否相等，注意’.‘
        if s and (s[0] == pattern[0] or pattern[0] == '.'):
            return match(s[1:], pattern[2:]) or \
                    match(s[1:], pattern) or \
                    match(s, pattern[2:])

        else:
            return match(s, pattern[2:])

    if s and (s[0]== pattern[0] or pattern[0] == '.'):
        return match(s[1:], pattern[1:])
    return False


if __name__ == '__main__':
    s = 'abcdsdsd'
    pattern = 'a.*d'
    print(match(s, pattern))




